package com.hardy.newSolutionAlgorithm;

import org.omg.PortableInterceptor.INACTIVE;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Author: fuxh3@lenovo.com
 * Date: Created in 2017/11/13 0013
 * 获取第n个丑数
 */
public class GetUglyNumber {
    public static void main(String[] args) {
        System.out.println(method1(1500));
        long startTime = System.currentTimeMillis();
        System.out.println(method2(1500));
        long endTime = System.currentTimeMillis();
        System.out.println((endTime-startTime)/1000);

    }
    public static int method1(int n){
        Queue<Integer> Q2=new LinkedList<>();
        Queue<Integer> Q3=new LinkedList<>();
        Queue<Integer> Q5=new LinkedList<>();
        Q2.add(2);
        Q3.add(3);
        Q5.add(5);
        int x=1;
        while (n-->1){
            x = Math.min(Math.min(Q2.peek(),Q3.peek()),Q5.peek());
            if(x==Q2.peek()){
                Q2.poll();
                Q2.add(x*2);
                Q3.add(x*3);
                Q5.add(x*5);
            }else if(x==Q3.peek()){
                Q3.poll();
                Q3.add(x*3);
                Q5.add(x*5);
            }else{
                Q5.poll();
                Q5.add(x*5);
            }
        }
        return x;
    }
    public static int method2(int n){
        int x=1;
        int i=0;
        while (true){
            if(valid(x)){
                i=i+1;
                if(i==n){
                    return x;
                }
            }
            x=x+1;
        }
    }
    public static boolean valid(int x){
        while (x%2==0){
            x=x/2;
        }
        while (x%3==0){
            x=x/3;
        }
        while (x%5==0){
            x=x/5;
        }
        if(x==1){
            return true;
        }else {
            return false;
        }
    }
}
